package sun.superstring;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 方式二：基于逆序数的方法来确保生成的布局是可解的。
public class SolvablePuzzleGenerator {

    public static void main(String[] args) {
        int size = 4; // 拼图大小，这里是4x4
        int[][] puzzle = generateSolvablePuzzle(size);
        printPuzzle(puzzle);
    }

    /**
     * 生成一个可解的拼图
     */
    private static int[][] generateSolvablePuzzle(int size) {
        List<Integer> tiles = new ArrayList<>();
        for (int i = 0; i < size * size - 1; i++) {
            tiles.add(i + 1); // 添加数字1到size*size-1
        }
        tiles.add(0); // 使用0代表空白块

        Collections.shuffle(tiles); // 随机打乱顺序

        while (!isSolvable(tiles, size)) { // 如果不可解，则重新打乱
            Collections.shuffle(tiles);
        }

        return to2DArray(tiles, size);
    }

    /**
     * 检查给定的一维数组表示的拼图是否可解
     */
    private static boolean isSolvable(List<Integer> tiles, int size) {
        int inversions = 0;
        int blankRow = 0;

        for (int i = 0; i < tiles.size(); i++) {
            if (tiles.get(i) == 0) {
                blankRow = size - (i / size); // 计算空白块距离底部的行数
                continue;
            }
            for (int j = i + 1; j < tiles.size(); j++) {
                if (tiles.get(j) != 0 && tiles.get(i) > tiles.get(j)) {
                    inversions++;
                }
            }
        }

        if (size % 2 == 1) { // 如果是奇数阶
            return inversions % 2 == 0;
        } else { // 偶数阶
            return (inversions + blankRow) % 2 != 0;
        }
    }

    /**
     * 将一维列表转换成二维数组
     */
    private static int[][] to2DArray(List<Integer> tiles, int size) {
        int[][] puzzle = new int[size][size];
        for (int i = 0; i < tiles.size(); i++) {
            puzzle[i / size][i % size] = tiles.get(i);
        }
        return puzzle;
    }

    /**
     * 打印拼图
     */
    private static void printPuzzle(int[][] puzzle) {
        for (int[] row : puzzle) {
            for (int tile : row) {
                System.out.print((tile == 0 ? "  " : String.format("%2d", tile)) + " ");
            }
            System.out.println();
        }
    }
}